class Solution:
    def maximalSquare(self, matrix: list) -> int:
        if not matrix:
            return 0
        res = 0
        self.matrix = matrix
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == "1" and (i, j):
                    res = max(res, self.search([[i, j]], [[i, j]], 1))
        return res

    def search(self, search_list_bottom, search_list_right, deepth):
        try:
            angle_point = [search_list_bottom[0][0] + 1, search_list_bottom[0][1] + deepth]
            if self.matrix[angle_point[0]][angle_point[1]] != "1":
                return deepth ** 2
        except:
            return deepth ** 2
        for i in range(deepth):
            search_list_bottom[i][0] += 1
            if self.matrix[search_list_bottom[i][0]][search_list_bottom[i][1]] != "1":
                break
            search_list_right[i][1] += 1
            if self.matrix[search_list_right[i][0]][search_list_right[i][1]] != "1":
                break
        else:
            search_list_bottom.append(angle_point[:])
            search_list_right.append(angle_point[:])
            return self.search(search_list_bottom, search_list_right, deepth + 1)
        return deepth ** 2


class Solution2:
    def maximalSquare(self, matrix: list) -> int:
        if not matrix:
            return 0
        res = 0
        for i in range(len(matrix)):
            matrix[i][0] = 1 if matrix[i][0] == "1" else 0
            res = max(res, matrix[i][0])
        for j in range(1, len(matrix[0])):
            matrix[0][j] = 1 if matrix[0][j] == "1" else 0
            res = max(res, matrix[0][j])
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == "1":
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
                    res = max(res, matrix[i][j])
                else:
                    matrix[i][j] = 0
        return res ** 2


a = Solution2()
print(a.maximalSquare([["1", "0", "1", "0", "0"],
                       ["1", "0", "1", "1", "1"],
                       ["1", "1", "1", "1", "1"],
                       ["1", "0", "0", "1", "0"]]))
print(a.maximalSquare([["1", "1", "1", "1"], ["1", "1", "1", "1"], ["1", "1", "1", "1"]]))
print(a.maximalSquare([["1","1"],["1","1"]]))
print(a.maximalSquare([["0", "0", "0", "1"],
                       ["1", "1", "0", "1"],
                       ["1", "1", "1", "1"],
                       ["0", "1", "1", "1"],
                       ["0", "1", "1", "1"]]))
